/**
设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key)
存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value)
如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

示例：

```c++
LRUCache cache = new LRUCache( 2 ); // 缓存容量

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);     // 返回  1
cache.put(3, 3);  // 该操作会使得密钥 2 作废
cache.get(2);     // 返回 -1 (未找到)
cache.put(4, 4);  // 该操作会使得密钥 1 作废
cache.get(1);     // 返回 -1 (未找到)
cache.get(3);     // 返回  3
cache.get(4);     // 返回  4
```
*/

/**
Solution:

通过链表的方式
*/

#pragma once

#include <iostream>
#include <list>
#include <memory>
#include <optional>
#include <stdexcept>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>

class cacheline {
   public:
    cacheline(int k, int v) : k(k), v(v), next(nullptr) { prev.reset(); }
    int k;
    int v;
    std::shared_ptr<cacheline> next;
    std::weak_ptr<cacheline> prev;
};

class LRUCache {
   public:
    LRUCache(int capacity) : capacity(capacity), head(nullptr), end(nullptr) {}

    // 链表的节点删除可以一个一个来，需要特判
    void removeNode(std::shared_ptr<cacheline>& node) {
        if (!node) return;

        // 处理前驱节点
        if (auto prev_sp = node->prev.lock()) {
            prev_sp->next = node->next;  // 前驱指向后继
        } else {
            // 如果 node 是 head，更新 head
            head = node->next;
        }

        // 处理后继节点
        if (node->next) {
            node->next->prev = node->prev;  // 后继指向前驱
        } else {
            // 如果 node 是 end，更新 end
            end = node->prev.lock();
        }

        // 断开 node 的连接
        node->prev.reset();
        node->next = nullptr;
    }

    // 其实直接放到链表尾部即可，因为后续被访问的会顶下去
    int get(int key) {
        try {
            auto c = index.at(key);
            if (c == end) {
                return c->v;
            }

            // 如果只有一个元素，可能导致 head 和 end 为空
            removeNode(c);

            if (end) {
                end->next = c;
                c->prev = end;
            } else {
                head = c;
            }
            end = c;
            return c->v;
        } catch (std::out_of_range& e) {
            // 返回 -1 未找到
            return -1;
        }
    }

    void put(int key, int value) {
        // 已存在，进行更新
        // 同时也是最近访问
        auto exists = index.find(key);
        if (exists != index.end()) {
            auto c = exists->second;
            c->v = value;
            if (c == end) {
                return;
            }

            // 如果只有一个元素，可能导致 head 和 end 为空
            removeNode(c);

            if (end) {
                end->next = c;
                c->prev = end;
            } else {
                head = c;
            }
            end = c;
            return;
        }

        // 若不存在
        auto c = std::make_shared<cacheline>(key, value);
        if (head == nullptr) {
            head = c;
            end = c;
            index.insert({key, c});
        } else if (index.size() < capacity) {
            end->next = c;
            c->prev = end;
            end = c;
            index.insert({key, c});
        } else {
            end->next = c;
            c->prev = end;
            end = c;
            index.insert({key, c});
            // delete head
            auto headk = head->k;
            head = head->next;
            index.erase(headk);
        }
    }

    void print() const {
        std::cout << "index with size " << index.size() << ": ";
        for (auto [k, v] : index) {
            std::cout << "{" << k << ", " << v->v << "}";
        }
        std::cout << std::endl << "list: ";
        auto iter = head;
        while (iter) {
            std::cout << "{" << iter->k << ", " << iter->v << "}";
            iter = iter->next;
        }
        std::cout << std::endl;
    }

   private:
    int capacity;
    std::unordered_map<int, std::shared_ptr<cacheline>> index;
    // C++
    // 中，若类型是对象类型（不是指针或者引用），会自动调用该类的默认构造函数
    std::shared_ptr<cacheline> head;
    std::shared_ptr<cacheline> end;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

std::vector<std::optional<int>> answer(
    int capacity, std::vector<std::tuple<std::string, int, int>> ops,
    bool print = false) {
    auto lrucache = LRUCache(capacity);
    std::vector<std::optional<int>> ret;
    for (auto op : ops) {
        auto [operation, key, value] = op;
        if (operation == "put") {
            lrucache.put(key, value);
            ret.push_back(std::nullopt);
        } else {
            ret.push_back(lrucache.get(key));
        }
        if (print) {
            lrucache.print();
        }
    }
    return ret;
}